SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Systolic array</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Systolic array</span></span>

</h1>

</header>

<p>

In <a href="Parallel_computing" title="Parallel computing">parallel</a> <a href="Computer_architectures" class="mw-redirect" title="Computer architectures">computer architectures</a>, a <b>systolic array</b> is a homogeneous <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">network</a> of tightly coupled <a href="Data_processing_unit" title="Data processing unit">data processing units</a> (DPUs) called cells or <a href="Node_(computer_science)" title="Node (computer science)">nodes</a>. Each node or DPU independently computes a partial result as a function of the data received from its upstream neighbours, stores the result within itself and passes it downstream. Systolic arrays were first used in <a href="Colossus_computer" title="Colossus computer">Colossus</a>, which was an early computer used to break German <a href="Lorenz_cipher" title="Lorenz cipher">Lorenz</a> ciphers during <a href="World_War_II" title="World War II">World War II</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Due to the classified nature of Colossus, they were independently invented or rediscovered by <a href="H._T._Kung" title="H. T. Kung">H. T. Kung</a> and <a href="Charles_Leiserson" class="mw-redirect" title="Charles Leiserson">Charles Leiserson</a> who described arrays for many dense linear algebra computations (matrix product, solving systems of <a href="Linear_equation" title="Linear equation">linear equations</a>, <a href="LU_decomposition" title="LU decomposition">LU decomposition</a>, etc.) for banded matrices. Early applications include computing <a href="Greatest_common_divisor" title="Greatest common divisor">greatest common divisors</a> of integers and polynomials.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Nowdays, they can be found in <a href="Neural_processing_unit" title="Neural processing unit">NPUs</a> and <a href="Hardware_accelerator" class="mw-redirect" title="Hardware accelerator">hardware accelerators</a> based on <a href="Spatial_architecture" title="Spatial architecture">spatial designs</a>. They are sometimes classified as <a href="Multiple_instruction%2C_single_data" title="Multiple instruction, single data">multiple-instruction single-data</a> (MISD) architectures under <a href="Flynn's_taxonomy" title="Flynn's taxonomy">Flynn's taxonomy</a>, but this classification is questionable because a strong argument can be made to distinguish systolic arrays from any of Flynn's four categories: <a href="Single_instruction%2C_single_data" title="Single instruction, single data">SISD</a>, <a href="Single_instruction%2C_multiple_data" title="Single instruction, multiple data">SIMD</a>, <a href="Multiple_instruction%2C_single_data" title="Multiple instruction, single data">MISD</a>, <a href="Multiple_instruction%2C_multiple_data" title="Multiple instruction, multiple data">MIMD</a>, as discussed later in this article.

</p><p>The parallel input <a href="Data" title="Data">data</a> flows through a network of hard-wired <a href="Microprocessor" title="Microprocessor">processor</a> nodes, which combine, process, <a href="Merge_algorithm" title="Merge algorithm">merge</a> or <a href="Sorting_algorithm" title="Sorting algorithm">sort</a> the input data into a derived result. Because the <a href="Wave" title="Wave">wave</a>-like propagation of data through a systolic array resembles the <a href="Pulse" title="Pulse">pulse</a> of the human circulatory system, the name <i>systolic</i> was coined from medical terminology. The name is derived from <a href="Systole" title="Systole">systole</a> as an analogy to the regular pumping of blood by the heart.

</p>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<p>Systolic arrays are often hard-wired for specific operations, such as <a href="Multiply%E2%80%93accumulate_operation" title="Multiply–accumulate operation">multiply and accumulate</a>, to perform massively <a href="Parallel_computing" title="Parallel computing">parallel</a> integration, <a href="Convolution" title="Convolution">convolution</a>, <a href="Correlation" title="Correlation">correlation</a>, <a href="Matrix_multiplication" title="Matrix multiplication">matrix multiplication</a> or data sorting tasks. They are also used for <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a> algorithms, used in DNA and protein <a href="Sequence_analysis" title="Sequence analysis">sequence analysis</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Architecture">Architecture</h2></div>

<p>A systolic array typically consists of a large <a href="Monolithic_system" title="Monolithic system">monolithic</a> <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">network</a> of primitive computing <a href="Node_(computer_science)" title="Node (computer science)">nodes</a> which can be hardwired or software configured for a specific application. The nodes are usually fixed and identical, while the interconnect is programmable. The more general <b>wavefront</b> processors, by contrast, employ sophisticated and individually programmable nodes which may or may not be monolithic, depending on the array size and design parameters. The other distinction is that systolic arrays rely on <a href="Synchronous" class="mw-redirect" title="Synchronous">synchronous</a> data transfers, while <a href="Wavefront" title="Wavefront">wavefront</a> tend to work <a href="https://en.wiktionary.org/wiki/asynchronous" class="extiw external" title="wikt:asynchronous">asynchronously</a>.

</p><p>Unlike the more common <a href="Von_Neumann_architecture" title="Von Neumann architecture">Von Neumann architecture</a>, where program execution follows a script of instructions stored in common memory, <a href="Address_space" title="Address space">addressed</a> and sequenced under the control of the <a href="CPU" class="mw-redirect" title="CPU">CPU</a>'s <a href="Program_counter" title="Program counter">program counter</a> (PC), the individual nodes within a systolic array are triggered by the arrival of new data and always process the data in exactly the same way. The actual processing within each node may be hard wired or block <a href="Microcode" title="Microcode">micro coded</a>, in which case the common node personality can be block programmable.

</p><p>The systolic array paradigm with data-streams driven by data <a href="Counter_(digital)" title="Counter (digital)">counters</a>, is the counterpart of the Von Neumann architecture with instruction-stream driven by a program counter. Because a systolic array usually sends and receives multiple data streams, and multiple data counters are needed to generate these data streams, it supports <a href="Data_parallelism" title="Data parallelism">data parallelism</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Goals_and_benefits">Goals and benefits</h2></div>

<p>A major benefit of systolic arrays is that all operand data and partial results are stored within (passing through) the processor array. There is no need to access external buses, main memory or internal caches during each operation as is the case with Von Neumann or <a href="Harvard_architecture" title="Harvard architecture">Harvard</a> sequential machines. The sequential limits on <a href="Parallel_computing" title="Parallel computing">parallel</a> performance dictated by <a href="Amdahl's_Law" class="mw-redirect" title="Amdahl's Law">Amdahl's Law</a> also do not apply in the same way, because data dependencies are implicitly handled by the programmable <a href="Node_(computer_science)" title="Node (computer science)">node</a> interconnect and there are no sequential steps in managing the highly parallel data flow.

</p><p>Systolic arrays are therefore extremely good at artificial intelligence, image processing, pattern recognition, computer vision and other tasks that animal brains do particularly well. Wavefront processors in general can also be very good at machine learning by implementing self configuring neural nets in hardware.

</p>

<div class="mw-heading mw-heading2"><h2 id="Classification_controversy">Classification controversy</h2></div>

<p>While systolic arrays are officially classified as <a href="Multiple_instruction%2C_single_data" title="Multiple instruction, single data">MISD</a>, their classification is somewhat problematic. Because the input is typically a vector

of independent values, the systolic array is definitely not <a href="Single_instruction%2C_single_data" title="Single instruction, single data">SISD</a>. Since these <a href="Input_(computer_science)" title="Input (computer science)">input</a> values are merged and combined into the result(s) and do not maintain their <a href="Independence" title="Independence">independence</a> as they would in a <a href="Single_instruction%2C_multiple_data" title="Single instruction, multiple data">SIMD</a> vector processing unit, the <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array</a> cannot be classified as such. Consequently, the array cannot be classified as a <a href="Multiple_instruction%2C_multiple_data" title="Multiple instruction, multiple data">MIMD</a> either, because MIMD can be viewed as a mere collection of smaller SISD and <a href="Single_instruction%2C_multiple_data" title="Single instruction, multiple data">SIMD</a> machines.

</p><p>Finally, because the data <a href="Swarm" class="mw-redirect" title="Swarm">swarm</a> is transformed as it passes through the array from <a href="Node_(computer_science)" title="Node (computer science)">node</a> to node, the multiple nodes are not operating on the same data, which makes the MISD classification a <a href="Misnomer" title="Misnomer">misnomer</a>. The other reason why a systolic array should not qualify as a <b>MISD</b> is the same as the one which disqualifies it from the SISD category: The input data is typically a vector not a <b>s</b>ingle <b>d</b>ata value, although one could argue that any given input vector is a single item of data.

</p><p>In spite of all of the above, systolic arrays are often offered as a classic example of MISD architecture in textbooks on <a href="Parallel_computing" title="Parallel computing">parallel computing</a> and in engineering classes. If the array is viewed from the outside as <a href="Atomic_operation" class="mw-redirect" title="Atomic operation">atomic</a> it should perhaps be classified as <b>SFMuDMeR</b> = single function, multiple data, merged result(s).

</p><p>Systolic arrays use a pre-defined computational flow graph that connects their nodes. <a href="Kahn_process_networks" title="Kahn process networks">Kahn process networks</a> use a similar flow graph, but are distinguished by the nodes working in lock-step in the systolic array: in a Kahn network, there are FIFO queues

between each node.

</p>

<div class="mw-heading mw-heading2"><h2 id="Detailed_description">Detailed description</h2></div>

<p>A systolic array is composed of matrix-like rows of <a href="Data_processing_unit" title="Data processing unit">data processing units</a> called cells. Data processing units (DPUs) are similar to <a href="Central_processing_unit" title="Central processing unit">central processing units</a> (CPUs), (except for the usual lack of a <a href="Program_counter" title="Program counter">program counter</a>,<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> since operation is <a href="Transport_triggered_architecture" title="Transport triggered architecture">transport-triggered</a>, i.e., by the arrival of a data object). Each cell shares the information with its neighbors immediately after processing. The systolic array is often rectangular where data flows across the array between neighbour <a href="Data_processing_unit" title="Data processing unit">DPUs</a>, often with different data flowing in different directions. The data streams entering and leaving the ports of the array are generated by auto-sequencing memory units, ASMs. Each ASM includes a data <a href="Counter_(digital)" title="Counter (digital)">counter</a>. In <a href="Embedded_system" title="Embedded system">embedded systems</a> a data stream may also be input from and/or output to an external source.

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .tmulti .multiimageinner{display:flex;flex-direction:column}.mw-parser-output .tmulti .trow{display:flex;flex-direction:row;clear:left;flex-wrap:wrap;width:100%;box-sizing:border-box}.mw-parser-output .tmulti .tsingle{margin:1px;float:left}.mw-parser-output .tmulti .theader{clear:both;font-weight:bold;text-align:center;align-self:center;background-color:transparent;width:100%}.mw-parser-output .tmulti .thumbcaption{background-color:transparent}.mw-parser-output .tmulti .text-align-left{text-align:left}.mw-parser-output .tmulti .text-align-right{text-align:right}.mw-parser-output .tmulti .text-align-center{text-align:center}@media all and (max-width:720px){.mw-parser-output .tmulti .thumbinner{width:100%!important;box-sizing:border-box;max-width:none!important;align-items:center}.mw-parser-output .tmulti .trow{justify-content:center}.mw-parser-output .tmulti .tsingle{float:none!important;max-width:100%!important;box-sizing:border-box;text-align:center}.mw-parser-output .tmulti .tsingle .thumbcaption{text-align:left}.mw-parser-output .tmulti .trow>.thumbcaption{text-align:center}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .tmulti .multiimageinner span:not(.skin-invert-image):not(.skin-invert):not(.bg-transparent) img{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .tmulti .multiimageinner span:not(.skin-invert-image):not(.skin-invert):not(.bg-transparent) img{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="thumb tmulti tright"><div class="thumbinner multiimageinner" style="width:384px;max-width:384px"><div class="trow"><div class="theader">Examples of 2x2 Matrix Multiplication in Systolic Array</div></div><div class="trow"><div class="tsingle" style="width:382px;max-width:382px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption">Systolic array algorithm accumulating output values inside <a href="Data_processing_unit" title="Data processing unit">DPUs</a>.</div></div></div><div class="trow"><div class="tsingle" style="width:382px;max-width:382px"><div class="thumbimage"><span typeof="mw:File"></span></div><div class="thumbcaption">Systolic array algorithm pre-loading and keeping one operand stationary inside <a href="Data_processing_unit" title="Data processing unit">DPUs</a> while computing. In the example, the green matrix is pre-loaded in the array and can be reused for subsequent multiplications.</div></div></div></div></div>

<p>An example of a systolic <a href="Algorithm" title="Algorithm">algorithm</a> might be designed for <a href="Matrix_multiplication" title="Matrix multiplication">matrix multiplication</a>. One <a href="Matrix_(mathematics)" title="Matrix (mathematics)">matrix</a> is fed in a row at a time from the top of the array and is passed down the array, the other matrix is fed in a column at a time from the left hand side of the array and passes from left to right. Dummy values are then passed in until each processor has seen one whole row and one whole column. At this point, the result of the multiplication is stored in the array and can now be output a row or a column at a time, flowing down or across the array.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p><p>Systolic arrays are arrays of <a href="Data_processing_unit" title="Data processing unit">DPUs</a> which are connected to a small number of nearest neighbour DPUs in a mesh-like topology. DPUs perform a sequence of operations on data that flows between them. Because the traditional systolic array synthesis methods have been practiced by algebraic algorithms, only uniform arrays with only linear pipes can be obtained, so that the architectures are the same in all DPUs. The consequence is, that only applications with regular data dependencies can be implemented on classical systolic arrays. Like <a href="Single_instruction%2C_multiple_data" title="Single instruction, multiple data">SIMD</a> machines, clocked systolic arrays compute in "lock-step" with each processor undertaking alternate compute | communicate phases. But systolic arrays with asynchronous handshake between DPUs are called <i>wavefront arrays</i>.

One well-known systolic array is Carnegie Mellon University's <a href="IWarp" title="IWarp">iWarp</a> processor, which has been manufactured by Intel. An iWarp system has a linear array processor connected by data buses going in both directions.

</p>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

<p>Systolic arrays (also known as <i>wavefront processors</i>), were first described by <a href="H._T._Kung" title="H. T. Kung">H. T. Kung</a> and <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. Leiserson</a>, who published the first paper describing systolic arrays in 1979. However, the first machine known to have used a similar technique was the <a href="Colossus_computer" title="Colossus computer">Colossus Mark II</a> in 1944.

</p>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Polynomial_evaluation">Polynomial evaluation</h3></div>

<p><a href="Horner's_rule" class="mw-redirect" title="Horner's rule">Horner's rule</a> for evaluating a polynomial is:

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y=(\ldots (((a_{n}\cdot x+a_{n-1})\cdot x+a_{n-2})\cdot x+a_{n-3})\cdot x+\ldots +a_{1})\cdot x+a_{0}.}</annotation>

</semantics>

</math></span><img src="./275e5001ad26c9aa87932423c61ebe646a8721fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:70.721ex; height:2.843ex;" alt="{\displaystyle y=(\ldots (((a_{n}\cdot x+a_{n-1})\cdot x+a_{n-2})\cdot x+a_{n-3})\cdot x+\ldots +a_{1})\cdot x+a_{0}.}" loading="lazy"></span></dd></dl>

<p>A linear systolic array in which the processors are arranged in pairs: one multiplies its input by <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> and passes the result to the right, the next adds <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{j}}</annotation>

</semantics>

</math></span><img src="./d0096fb78d6843c9fb67a840dc796b61ad93eec2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.14ex; height:2.343ex;" alt="{\displaystyle a_{j}}" loading="lazy"></span> and passes the result to the right.

</p>

<div class="mw-heading mw-heading3"><h3 id="Convolution">Convolution</h3></div>

<p>Consider a chain of processing elements (PEs), each performing a <a href="Multiply%E2%80%93accumulate_operation" title="Multiply–accumulate operation">multiply-accumulate operation</a>. It processes input data (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math></span><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"></span>) and weights (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{i}}</annotation>

</semantics>

</math></span><img src="./fe22f0329d3ecb2e1880d44d191aba0e5475db68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.464ex; height:2.009ex;" alt="{\displaystyle w_{i}}" loading="lazy"></span>) systolically, meaning data flows through the array in a regular, rhythmic manner. The weights remain stationary within each PE, while the input data and partial sums (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}}</annotation>

</semantics>

</math></span><img src="./67d30d30b6c2dbe4d6f150d699de040937ecc95f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.939ex; height:2.009ex;" alt="{\displaystyle y_{i}}" loading="lazy"></span>) move in opposite directions.

</p><p>Each PE performs the following operation:<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}y_{out}&=y_{in}+w\cdot x_{in}\\x_{out}&=x_{in}\end{aligned}}}">

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}y_{out}&=y_{in}+w\cdot x_{in}\\x_{out}&=x_{in}\end{aligned}}}</annotation>

</semantics>

</math></span></span>where:

</p>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{in}}</annotation>

</semantics>

</math></span><img src="./c8c792be9821fb9c617b3a0963e52fa0d9244975.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.116ex; height:2.009ex;" alt="{\displaystyle x_{in}}" loading="lazy"></span> is the input data.</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{in}}</annotation>

</semantics>

</math></span><img src="./8524dd32682861d31a0d433d0d8db5ec56962305.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.925ex; height:2.009ex;" alt="{\displaystyle y_{in}}" loading="lazy"></span> is the incoming partial sum.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math></span><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"></span> is the weight stored in the PE.</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{out}}</annotation>

</semantics>

</math></span><img src="./131dfa676ac16f07cd9d02f830ef024401a8ddf1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.893ex; height:2.009ex;" alt="{\displaystyle x_{out}}" loading="lazy"></span> is the output data (passed to the next PE).</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{out}}</annotation>

</semantics>

</math></span><img src="./86257ef9e4fa9e2fe4bc39b9540218e5c4bc3b02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.703ex; height:2.009ex;" alt="{\displaystyle y_{out}}" loading="lazy"></span> is the updated partial sum.</li></ul>

<p>From the left, the input stream is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \dots ,x_{3},0,x_{2},0,x_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \dots ,x_{3},0,x_{2},0,x_{1}}</annotation>

</semantics>

</math></span><img src="./398c20834a80dab1c0953ba2312fa6fa87c48600.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.757ex; height:2.509ex;" alt="{\displaystyle \dots ,x_{3},0,x_{2},0,x_{1}}" loading="lazy"></span>, and from the right, the output stream is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1},y_{2},y_{3},\dots }">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1},y_{2},y_{3},\dots }</annotation>

</semantics>

</math></span><img src="./aaf2e01653b4248cef6fd1fc4d783857b5018900.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.405ex; height:2.009ex;" alt="{\displaystyle y_{1},y_{2},y_{3},\dots }" loading="lazy"></span>. If <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1},x_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1},x_{1}}</annotation>

</semantics>

</math></span><img src="./debea7627124cf08ca2fe529c41912cbea30647a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.611ex; height:2.009ex;" alt="{\displaystyle y_{1},x_{1}}" loading="lazy"></span> enter the rightmost PE simultaneously, then the leftmost PE outputs<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}y_{1}&=w_{1}x_{1}+w_{2}x_{2}+w_{3}x_{3}+\cdots \\y_{2}&=w_{1}x_{2}+w_{2}x_{3}+w_{3}x_{4}+\cdots \\&\vdots \end{aligned}}}">

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}y_{1}&=w_{1}x_{1}+w_{2}x_{2}+w_{3}x_{3}+\cdots \\y_{2}&=w_{1}x_{2}+w_{2}x_{3}+w_{3}x_{4}+\cdots \\&\vdots \end{aligned}}}</annotation>

</semantics>

</math></span></span>This is the 1-dimensional convolution. Similarly, n-dimensional convolution can be computed by an n-dimensional array of PEs.

</p><p>Many other implementations of the 1D convolutions are available, with different data flows.<sup id="cite_ref-:0_5-0" class="reference"><a href="#cite_note-:0-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p><p>See <sup id="cite_ref-:0_5-1" class="reference"><a href="#cite_note-:0-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> Figure 12 for an algorithm that performs on-the-fly <a href="Least_squares" title="Least squares">least-squares</a> using one- and two-dimensional systolic arrays.

</p>

<div class="mw-heading mw-heading3"><h3 id="Sorting">Sorting</h3></div>

<p><a href="Bubble_sort" title="Bubble sort">Bubble sort</a> is also an example of 1D systolic computation,<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> although it applies N-1 passes for an array of size N. Each pass systolically moves the maximum element of a subsequence towards its final location in the sorted result.

</p><p>If one is willing to use N/2 processing elements (PE) each with a comparator and two registers, elements arranged in a stack-like fashion, an array (or stream) of size N can thus be sorted in 2N time by pushing its elements in while on every level of the systolic stack the maximum of the pair of elements stored in each PE is pushed further down. And after all the elements are pushed in, the process is reversed with the minimum element in each PE being popped out (or "pushed up"), resulting in the stream of elements coming out sorted in ascending order.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p><p>Sorting input arrays of larger size (N > P) than the number of processing elements (P) is somewhat complex to do efficiently with such a system, but can be realized (by adding an external serial processor) in O(N log N/log P) time. The serial processor needs to manage a "bucket B-tree", where each node in the <a href="B-tree" title="B-tree">B-tree</a> has P "buckets" that are eventually each sorted in O(P) time using the PEs.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Implementations">Implementations</h2></div>

<ul><li>Inmos <a href="Transputer" title="Transputer">Transputer</a><sup id="cite_ref-HSP_9-0" class="reference"><a href="#cite_note-HSP-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Cisco" title="Cisco">Cisco</a> PXF network processor is internally organized as systolic array.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup></li>

<li>Google’s <a href="Tensor_Processing_Unit" title="Tensor Processing Unit">TPU</a> is also designed around a systolic array.</li>

<li>Paracel FDF4T TestFinder text search system<sup id="cite_ref-FDF4_11-0" class="reference"><a href="#cite_note-FDF4-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup></li>

<li>Paracel FDF4G GeneMatcher Biological (DNA and Protein) search system</li>

<li>Inferentia chip at <a href="Amazon_Web_Services" title="Amazon Web Services">Amazon Web Services</a><sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup></li>

<li>Gemmini systolic array-based accelerator developed at <a href="UC_Berkeley" class="mw-redirect" title="UC Berkeley">UC Berkeley</a><sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup></li></ul>

<ul><li><a href="Multiple_instruction%2C_single_data" title="Multiple instruction, single data">MISD</a> – multiple instruction single data, example: systolic arrays</li>

<li><a href="IWarp" title="IWarp">iWarp</a> – systolic array computer, VLSI, Intel/CMU</li>

<li><a href="WARP_(systolic_array)" title="WARP (systolic array)">WARP (systolic array)</a> – systolic array computer, GE/CMU</li>

<li><a href="Tensor_Processing_Unit" title="Tensor Processing Unit">Tensor Processing Unit</a> – <a href="AI" class="mw-redirect" title="AI">AI</a> accelerator <a href="ASIC" class="mw-redirect" title="ASIC">ASIC</a></li>

<li><a href="Spatial_architecture" title="Spatial architecture">Spatial architecture</a> - class of computer architectures encompassing systolic arrays</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=g2tMcMQqSbA&t=41m45s"><span class="">Colossus - The Greatest Secret in the History of Computing</span></a> on <a href="YouTube_video_(identifier)" class="mw-redirect" title="YouTube video (identifier)">YouTube</a></span>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBrentKung1984" class="citation web cs1">Brent, Richard P.; Kung, H.T. (August 1984). <a rel="nofollow" class="external text" href="http://www.eecs.harvard.edu/~htk/publication/1984-ieeetoc-brent-kung.pdf">"Systolic VLSI Arrays for Polynomial GCD Computation"</a> <span class="cs1-format">(PDF)</span>. <i>www.eecs.harvard.edu</i>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">The Paracel GeneMatcher series of systolic array processors do have a <a href="Program_counter" title="Program counter">program counter</a>. More complicated algorithms are implemented as a series of simple steps, with shifts specified in the instructions.</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://web.cecs.pdx.edu/~mperkows/temp/May22/0020.Matrix-multiplication-systolic.pdf">"Systolic Array Matrix Multiplication"</a> <span class="cs1-format">(PDF)</span>.</cite></span>

</li>

<li id="cite_note-:0-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_5-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFKung1982" class="citation journal cs1">Kung (January 1982). <a rel="nofollow" class="external text" href="https://www.semanticscholar.org/paper/Why-systolic-architectures-Kung/256bbe8e9fa3f5b72c24f1037ab734f9e7dd01c4">"Why systolic architectures?"</a>. <i>Computer</i>. <b>15</b> (1): <span class="nowrap">37–</span>46. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FMC.1982.1653825">10.1109/MC.1982.1653825</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0018-9162">0018-9162</a>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text">C.L. Britton, Jr., M.N. Ericson, and D.W. Bouldin, "A Virtual Zero-Time, Monolithic Systolic Sorting Array", 1989 <a rel="nofollow" class="external free" href="https://www.osti.gov/servlets/purl/6004774">https://www.osti.gov/servlets/purl/6004774</a></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text">M. H. Alsuwaiyel, *Parallel Algorithms*, World Scientific, 2022, Sec. 9.5 "An On-chip Bubble Sorter" (in Ch. 9 "Systolic Computation").</span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text">Mikhail J. Atallah, Greg N. Frederickson, S. Rao Kosaraju, "Sorting with efficient use of special-purpose sorters", Information Processing Letters 1988 <a rel="nofollow" class="external free" href="https://doi.org/10.1016/0020-0190(88)90075-0">https://doi.org/10.1016/0020-0190(88)90075-0</a>; also as Purdue CSD-TR 87-695 <a rel="nofollow" class="external free" href="https://docs.lib.purdue.edu/cstech/602/">https://docs.lib.purdue.edu/cstech/602/</a></span>

</li>

<li id="cite_note-HSP-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-HSP_9-0">^</a></b></span> <span class="reference-text">"Systolic Arrays" in *Handbook of Signal Processing Systems* (3rd ed.), 2018

<a rel="nofollow" class="external free" href="https://link.springer.com/chapter/10.1007/978-3-319-91734-4_26">https://link.springer.com/chapter/10.1007/978-3-319-91734-4_26</a></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.cisco.com/en/US/products/hw/routers/ps133/prod_installation_guide09186a0080525aba.html#wp48065">"Cisco 10000 Series Router Performance Routing Engine Installation"</a><span class="reference-accessdate">. Retrieved <span class="nowrap">3 August</span> 2020</span>.</cite></span>

</li>

<li id="cite_note-FDF4-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-FDF4_11-0">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://brandprosgroup.com/pages/first/websites/paracel/data/html/about_paracel2.html">"About Paracel"</a>. <i>brandprosgroup.com</i>. Paracel<span class="reference-accessdate">. Retrieved <span class="nowrap">4 May</span> 2018</span>.</cite></span>

</li>

<li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://aws.amazon.com/blogs/aws/amazon-ecs-now-supports-ec2-inf1-instances/">"Announcing availability of Inf1 instances in Amazon SageMaker for high performance and cost-effective machine learning inference"</a>. 14 August 2020<span class="reference-accessdate">. Retrieved <span class="nowrap">15 August</span> 2020</span>.</cite></span>

</li>

<li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><cite id="CITEREFGencKimAmidHaj-Ali2021" class="citation book cs1">Genc, Hasan; Kim, Seah; Amid, Alon; Haj-Ali, Ameer; Iyer, Vighnesh; Prakash, Pranav; Zhao, Jerry; Grubb, Daniel; Liew, Harrison; Mao, Howard; Ou, Albert; Schmidt, Colin; Steffl, Samuel; Wright, John; Stoica, Ion; Ragan-Kelley, Jonathan; Asanovic, Krste; Nikolic, Borivoje; Shao, Yakun Sophia (2021). "Gemmini: Enabling Systematic Deep-Learning Architecture Evaluation via Full-Stack Integration". <i>2021 58th ACM/IEEE Design Automation Conference (DAC)</i>. pp. <span class="nowrap">769–</span>774. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1911.09925">1911.09925</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FDAC18074.2021.9586216">10.1109/DAC18074.2021.9586216</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-6654-3274-0</bdi>.</cite></span>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<ul><li>H. T. Kung, C. E. Leiserson: Algorithms for VLSI processor arrays; in: C. Mead, L. Conway (eds.): Introduction to VLSI Systems; Addison-Wesley, 1979</li>

<li>S. Y. Kung: VLSI Array Processors; Prentice-Hall, Inc., 1988</li>

<li>N. Petkov: Systolic Parallel Processing; North Holland Publishing Co, 1992</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><cite id="CITEREFDorbandHemsendorfMerritt2003" class="citation journal cs1">Dorband, Ernst Nils; Hemsendorf, Marc; <a href="David_Merritt" title="David Merritt">Merritt, David</a> (March 2003). <a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/abs/pii/S0021999102000670">"Systolic and hyper-systolic algorithms for the gravitational n-body problem, with an application to Brownian motion"</a>. <i>Journal of Computational Physics</i>. <b>185</b> (2): <span class="nowrap">484–</span>511.</cite></li>

<li><a rel="nofollow" class="external text" href="http://www.iti.fh-flensburg.de/lang/papers/isa/index.htm"><i>Instruction Systolic Array (ISA)</i></a></li>

<li><a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4292156">'A VLSI Architecture for Image Registration in Real Time' (Based on systolic array), Vol. 15, September 2007</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-08-01" href="https://en.wikipedia.org/wiki/?title=Systolic_array&oldid=1303713446">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>